/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv
   @Language: C++
   @Datetime: 20-01-03 16:45
   */

// Method 1, using global, local dp. Time O(n*k), Space O(n*k), Time 101ms
class Solution {
	int maxProfit(vector<int> &prices){
		int profit=0;
		for(int i=1; i<prices.size(); ++i)
			profit+=max(0,prices[i]-prices[i-1]);
		return profit;
	}
public:
	/**
	 * Tip:
	 * global[i][j]: range [0,i] exchange j times, max profit
	 * local[i][j]: range [0,i] exchange j times and last exchange must at j, local profit
	 */
	int maxProfit(int k, vector<int> &prices) {
		int n=prices.size();
		if(k>=n/2) return maxProfit(prices);
		vector<vector<int> > global(n,vector<int>(k+1,0)), local(n,vector<int>(k+1,0));
		for(int i=1; i<n; ++i){
			const int diff=prices[i]-prices[i-1];
			for(int j=1; j<=k; ++j){
				local[i][j]=max(global[i-1][j-1]+max(0,diff),local[i-1][j]+diff);
				global[i][j]=max(global[i-1][j],local[i][j]);
			}
		}
		return global[n-1][k];
	}
};


// Method 2, using global, local dp with compress state. Time O(n*k), Space O(k), Time 50ms
class Solution {
	int maxProfit(vector<int> &prices){
		int profit=0;
		for(int i=1; i<prices.size(); ++i)
			profit+=max(0,prices[i]-prices[i-1]);
		return profit;
	}
public:
	int maxProfit(int k, vector<int> &prices) {
		int n=prices.size();
		if(k>=n/2) return maxProfit(prices);
		vector<int> global(k+1,0), local(k+1,0);
		for(int i=1; i<n; ++i){
			const int diff=prices[i]-prices[i-1];
			for(int j=k; j; --j){
				local[j]=max(global[j-1]+max(0,diff),local[j]+diff);
				global[j]=max(global[j],local[j]);
			}
		}
		return global[k];
	}
};
